Embodiments generally relate to content addressable memories, and more particularly to storing data in ternary content addressable memories.
A content addressable memory (CAM) is a storage device typically used for storing data words. A CAM generally stores a large number of data words, e.g., 32K words. In addition, a CAM data word generally includes a relatively large number of bits, e.g., 36 to 144 bits. The bits stored in a CAM data word may be addressed in two ways. First, each bit in a CAM may be addressed according to a uniquely identifiable storage element. For example, each CAM data word may have a row address and each bit in a word may have a column address. Second, a CAM data word may be addressed by the content of the data word. It is this later method of addressing that makes a CAM useful in certain applications.
Addressing a CAM data word by content involves comparing a search word with all of the CAM data words stored in the CAM. The search word may be compared with all with all of the CAM data words in parallel. For example, a CAM may be used to store network addresses. A CAM used for storing network addresses might store 32K data words, each word being a 144 bit address. The CAM might be used in a network router and the CAM would enable an address of a data packet received by the router to be compared with all of the addresses stored in the CAM. Typically, a search word can be compared with all of the stored CAM data words in a single cycle. If the search word identically matches one or more of the stored CAM data words, a match line corresponding with the CAM data word is asserted. The match lines may be fed to a match line sense amplifier having its output coupled with an encoder. The encoder generates a match location corresponding with the match line of the matching CAM data word. Continuing the example of CAM data words being network addresses, the match location may identify a destination where a data packet should be forwarded.
A ternary CAM (TCAM) is a variation on a CAM. While a CAM requires that the search word identically match a stored CAM data word, a TCAM does not require that the search word identically match a stored TCAM data word. This is because a TCAM provides two bits for each bit of the search word, whereas a CAM provides a single bit. The two bits per search word bit allow a TCAM to store a code that may represent a logic 1, a logic 0, or both a logic 1 and a logic 0. When a stored bit of a TCAM word represents both a logic 1 and a logic 0, it may be denoted by an “X” and referred to as a “don't care” value. Accordingly, if the TCAM code corresponding with a bit of a search word data is an X, the search word bit will always match the TCAM code, regardless of whether the search word bit is a logic 1 or a logic 0. Other than this capability to store “don't care” values, a TCAM may function similarly to a CAM.